package code_capriccio;

import java.util.*;



// 代码随想录（单调栈）
public class Demo12 {


    //739. 每日温度
    public int[] dailyTemperatures(int[] t) {
        int n = t.length;
        int[] answer = new int[n];
        Deque<Integer> st = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && t[i] > t[st.peek()]) {
                int index = st.pop();
                answer[index] = i - index;
            }
            st.push(i);
        }
        return answer;
    }



    //496. 下一个更大元素 I
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> hash = new HashMap<>();    // 记录 nums1 中的元素值、下标
        for(int i = 0; i < nums1.length; i++) hash.put(nums1[i], i);

        Deque<Integer> st = new LinkedList<>();  // 存放nums2元素值
        int[] ret = new int[nums1.length];
        Arrays.fill(ret, -1);

        for(int i = 0; i < nums2.length; i++) {
            while(!st.isEmpty() && nums2[i] > st.peek()) {
                int val = st.pop();
                if(hash.containsKey(val)) {
                    ret[hash.get(val)] = nums2[i];
                }
            }
            st.push(nums2[i]);
        }
        return ret;
    }



    //503. 下一个更大元素 II
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> st = new LinkedList<>();     // 存放元素的下标

        for(int i = 0; i < n * 2 ; i++) {
            while(!st.isEmpty() && nums[i % n] > nums[st.peek() % n]) {
                int index = st.pop();
                ret[index] = nums[i % n];
            }
            st.push(i % n);
        }
        return ret;
    }



    //42. 接雨水(单调栈解法）
    public int trap(int[] height) {
        // 单调栈：递增栈，求右边第一个 比 当前位置高的柱子
        Deque<Integer> stack = new LinkedList<>();
        int ret = 0;
        for(int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int mid = stack.pop();
                if(stack.isEmpty()) break;

                int width = i - stack.peek() - 1;
                int high = Math.min(height[i], height[stack.peek()]) - height[mid];
                ret += width * high;
            }
            if(!stack.isEmpty() && height[stack.peek()] == height[i]) stack.pop();
            stack.push(i);
        }
        return ret;
    }

    //public int trap(int[] height) {
    //        // 按每一列求雨水的面积
    //        // 先用 dp 表保存每个位置 左边和右边最高柱子的高度，避免重复计算
    //        int n = height.length;
    //        int[] left_dp = new int[n], right_dp = new int[n];
    //        left_dp[0] = right_dp[n - 1] = 0;
    //        for(int i = 1; i < n; i++) left_dp[i] = Math.max(height[i - 1], left_dp[i - 1]);
    //        for(int i = n - 2; i >= 0; i--) right_dp[i] = Math.max(height[i + 1], right_dp[i + 1]);
    //
    //        int ret = 0;
    //        for(int i = 1; i < n - 1; i++) {    // 第1列和最后一列不能接雨水,不用计算
    //            // max_left 和 max_right 中的较小值比 height[i] 大， 则更新结果
    //            int minHeight = Math.min(left_dp[i], right_dp[i]);
    //            if(minHeight > height[i]) ret += minHeight - height[i];
    //        }
    //        return ret;
    //    }
}
